#ifndef GRAPH_H
#define GRAPH_H

#include "gisgraphlib_global.h"
#include "vertex.h"
#include "edge.h"
#include <QHash>
#include <QPair>
#include <QList>
#include <QVector>
#include <QSharedData>
#include <QSharedDataPointer>

class GraphPrivate : public QSharedData
{
public:
	GraphPrivate() : QSharedData(), currentName(0), hamilton_cycles(), minimal_route(-1) { }
	GraphPrivate(const GraphPrivate &other) : QSharedData(other) { }
	QHash<Vertex, QList<Edge> > adjacencyMap;
	QList<QPair<int, QList<Vertex> > > hamilton_cycles;
	int minimal_route;
	mutable QList<Vertex> visited;
	char *currentName;

	bool isConnected_helper() const;
	void dfsTraverseFrom(Vertex v) const;
	QList<Vertex> vertices() const;
	QList<Vertex> vertices(Vertex v) const;
	QString generateName();
	void resetNameGenerator();
};

class GISGRAPHLIBSHARED_EXPORT Graph
{
public:
	Graph();
	Graph(const Graph &other);
	Graph &operator=(const Graph &other);
	QList<Vertex> vertices() const;
	QList<Vertex> vertices(Vertex v) const;
	QList<Edge> edges() const;
	QList<Edge> edges(Vertex v) const;
	int length(Vertex a, Vertex b) const;
	bool addVertex(Vertex v);
	bool addEdge(Edge e);
	bool addEdge(Vertex vBeg, Vertex vEnd, int length);
	bool addEdge(const QString &vBegin, const QString &vEnd, int length);
	bool isConnected() const;
	// barabasz
	void createGraph(int vertex_no,	int lvl = 0);
	void preciseSalesman();
	int preciseSalesmanIter(const Vertex &v, QList<Vertex> visited, int route);
	QVector<QString> heuristicSalesman();

	QList<Vertex> route();

private:
	QSharedDataPointer<GraphPrivate> d;
};

#endif // GRAPH_H
